
// 1.链表-160-相交链表
// 2.链表-206-反转链表
// 3.链表-92-反转链表2mn 
// 4.链表-24-两两交换链表中的节点
// 5.链表-25-k个一组翻转链表
// 6.链表-19-删除链表的倒数第n个节点
// 7.链表-141-环形链表
// 8.链表-142-环形链表2
// 9.链表-234-回文链表

// 10.链表-21-合并两个有序链表
// 11。链表-23-合并k个升序链表
// 12.链表-2-两数相加
// 13.链表-148-排序链表
// 14.链表-138-复制带随机指针的链表






// 1.相交链表
var getIntersectionNode = function (headA, headB) {
  // 走两次，同时到达终点
  let pA = headA;
  let pB = headB;

  while (pA || pB) {
    if (pA === pB) return pA
    pA = pA === null ? headB : pA.next
    pB = pB === null ? headA : pB.next
  }

  return null
};



// 2.翻转链表
var reverseList = (head) => {
  let pre = null
  let cur = head
  while (cur) {
    let next = cur.next;
    cur.next = pre; // 翻转箭头
    pre = cur; // 下移动
    cur = next; // 下移动
  }
  return pre
}

// 3.翻转链表mn
var reverseListMN = (head, m, n) => {
  let dummy = new ListNode(0);
  dummy.next = head;

  // 找到第m个节点位置
  let prev = dummy;
  for (let i = 0; i < m - 1; i++) { // 保证目标前一个
    prev = prev.next;
  }

  let cur = prev.next;
  for (let i = 0; i < n - m ; i++) {
    let next = cur.next;
    cur.next = next.next; // 
    next.next = prev.next; // 
    prev.next = next; // 
  }

  return dummy.next;
}

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

let l1 = new ListNode(1)
let l2 = new ListNode(2)
let l3 = new ListNode(3)
let l4 = new ListNode(4)
let l5 = new ListNode(5)
let l6 = new ListNode(6)
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;

console.log(swapPairs(l1, 2, 4))





// 4.两两交换链表中的节点 1234 2143
var swapPairs = function (head) {
  let dummy = new ListNode();
  dummy.next = head;


  let prev = dummy;

  while (head && head.next) {
    const next = head.next
    head.next = next.next
    next.next = prev.next
    prev.next = next

    prev = head
    head = head.next
  }

  return dummy.next

};




// 5.k个一组翻转链表
var reverseKGroup = function (head, k) {
  if (!head || !head.next) return head;

  let dummy = new ListNode()
  dummy.next = head

  let prev = dummy;
  let curr = head;
  let next2;

  // 求长度用于循环
  let lHead = head;
  let len = 0;
  while (lHead != null) {
    len++
    lHead = lHead.next;
  }

  console.log(len/k)
  let n = Math.floor(len / k)
  while(n--){
    for (let j = 0; j < k - 1; j++) {

      next2 = curr.next;
      curr.next = next2.next;
      next2.next = prev.next; //
      prev.next = next2;
    }

    prev = curr
    curr = prev.next
    console.log(prev, curr)
    
  }
    
  return dummy.next
};



// 6.删除链表的倒数第k个
// 正反
var findListK = (head, k) => {
  if (!head || k < 0) return null;

  let headA = head;
  let headB = head;

  // 截取正数k个
  while (k) {
    if (headA.next) {
      headA = headA.next;
      k--
    } else {
      return null
    }
  }

  // headA 余（总数-k）headB是从头 所以是倒数k个
  while (headA) {
    headA = headA.next
    headB = headB.next
  }
  return headB
}
// 删除链表的倒数第n个节点
// var removeNthFromEnd = function (head, n) {
//   let pre = new ListNode()
//   pre.next = headc
//   let headA = pre
//   let headB = pre
//   while (n) { // 这里多处理一次
//     if (headA.next) {
//       headA = headA.next
//       n--
//     } else {
//       return null
//     }
//   }

//   while (headA.next) { // 这里少一次
//     headA = headA.next
//     headB = headB.next
//   }

//   // headb 目前是第k位的前一个
//   headB.next = headB.next.next
//   return pre.next // 不可以直接返回head
// };


// 7.环形链表- 是否有环
// 加tag
var hasCircle = (head) => {
  while (head) {
    if (head.tag) return true;
    head.tag = true
    head = head.next
  }
  return false
}

// 8.环形链表2 - 找到成环的节点
// map
var detectCycle = (head) => {
  if (!head) return null;
  var map = new WeakMap();

  while (head.next) {
    if (map.get(head.next)) {
      return head.next
    }
    map.set(head, true)
    head = head.next
  }
  return null
}

// 9.回文链表
// 转换为数组问题
var isPalindrome = (head) => {
  const vals = []
  while (head !== null) {
    vals.push(head.val)
    head = head.next
  }

  let left = 0;
  let right = vals.length - 1;
  while (left < right) {
    if (head[left++] !== head[right--]) {
      return false
    }
  }
  return true;
}

// 10.合并两个有序 - 递归去解决
var mergeTwoLists = (l1, l2) => {
  if (l1 === null) return l2
  if (l2 === null) return l1
  // 谁大用谁，用过的继续递归，直至终止条件
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}

// 11.合并k个升序
// 将链表问题转换为数组问题，重新构造链表
var mergeKLists = (lists) => {
  function transform(l, arr) {
    while (l) {
      arr.push(l.val)
      l = l.next
    }
  }

  let arr = [];
  let res = new ListNode();

  lists.map(item => transform(item, arr))
  arr.sort((a, b) => a - b)
  // 这里注意创建关联关系，需要先构造后面的
  for (let i = arr.length - 1; i >= 0; i--) {
    let temp = new ListNode(null)
    res.val = arr[i]
    temp.next = res
    res = temp
  }
  return res.next
}


// 12.链表-2-两数相加
// 注意补充进位
var addTwoNumbers = function (l1, l2) {
  let temp = new ListNode(null)
  let head = temp
  let addOne = 0  // 存进位

  while (l1 || l2 || addOne) {
    let v1 = l1 ? l1.val : 0
    let v2 = l2 ? l2.val : 0
    let sum = v1 + v2 + addOne  // 计算进位
    addOne = sum >= 10 ? 1 : 0 // 补充进位
    temp.next = new ListNode(sum % 10)
    temp = temp.next
    if (l1) l1 = l1.next
    if (l2) l2 = l2.next
  }
  return head.next
};



// 13.链表-148-排序链表（归并排序）
var sortList = function (head) {
  if (head == null || head.next == null) return head;
  // 快慢找到中间结点
  let fast = head.next
  let slow = head

  while (fast !== null && fast.next !== null) { // fast 每次两步，避免越界
    slow = slow.next
    fast = fast.next.next
  }

  let temp = slow.next // 右起点
  slow.next = null  // 左边截断

  let left = sortList(head)
  let right = sortList(temp)

  // 然后是两个有序链表的合并
  let h = new ListNode();
  let res = h; // 暂存的最初始的结点node地址
  while (left !== null && right !== null) {
    if (left.val < right.val) { // 
      h.next = left;
      left = left.next
    } else {
      h.next = right
      right = right.next
    }
    h = h.next
  }
  h.next = left != null ? left : right
  return res.next
};


// 14.复制带随机指针的链
var copyRandomList = function(head) {
  if(!head) return head
  let cur = head;
  const map = new Map();

  // 第一次遍历生成一个value属性的链表
  while(cur){
      map.set(cur, new Node(cur.val))
      cur = cur.next
  }

  // 第二次遍历，根据map映射关系，将
  cur = head;
  while(cur){
      map.get(cur).next = map.get(cur.next) || null
      map.get(cur).random = map.get(cur.random) || null
      cur = cur.next
  }

  return map.get(head)
  
};
